#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

class Comp1 {
  private:
    const string& text;

  public:
    Comp1(const string& str) : text(str) {}
    bool operator() (int i, int j) { return text[i] < text[j]; }
};


class Comp2 {
  private:
    const vector<int>& c;
    int size;
    int l;

  public:
    Comp2(vector<int>& v, int sz, int i) : c(v), size(sz), l(i) {}
    bool operator() (int i, int j) {
        if (c[i] != c[j]) return c[i] < c[j];

        if (i + l < size && j + l < size) return c[i + l] < c[j + l];

        return (i + l >= size || j + l < size);
    }
};

int sufCompare(const char* a, const char* b, int n, bool& anySame) {
    int same = 0;

    while (same < n) {
        if (*a == *b) same++;
        else break;
        a++;
        b++;
    }

    anySame = same > 0;

    if (same == n) { return 0; };

    if (*a > *b) return anySame ? same : 1;
    return anySame ? -same : -1;
}

void binSearch(vector<int> suf, const string& text, const string& value, int l, int r, int lSame = 0, int rSame = 0) {
    int left = l;
    int right = r;
    int lastSame = min(lSame, rSame);
    int cmp = 0;

    while (l <= r) {
        int m = (l + r) / 2;
        int n = min(text.size() - suf[m] - lastSame, value.size() - lastSame);
        bool anySame;
        cmp = sufCompare(&text[suf[m] + lastSame], &value[lastSame], n, anySame);

        if (cmp == 0 && anySame) {
            cout<<suf[m]<<endl;
            binSearch(suf, text, value, left, m - 1, lSame, lastSame);
            binSearch(suf, text, value, m + 1, right, lastSame, rSame);
            return;
        } else {
            if (anySame) { lastSame += abs(cmp); }

            if (cmp > 0) { r = m - 1; }
            else { l = m + 1; }
        }
    }
}

void getSufArray(vector<int>& suf, const string& s) {
    int size = s.size();
    int sizeLog = (int) ceil(log((double)size) / log(2.0)) - 1;
    vector<int> c(size);

    suf.resize(size);
    for (int i = 0; i < size; ++i) suf[i] = i;
    sort(suf.begin(), suf.end(), Comp1(s));

    for (int i = 0; i < size; ++i) c[i] = s[i];

    for (int i = 0, l = 2; i <= sizeLog; ++i, l *= 2) {
        sort(suf.begin(), suf.end(), Comp2(c, size, l));

        c[suf[0]] = 0;
        for (int j = 1; j < size; ++j) {
            int l1 = suf[j - 1];
            int r1 = suf[j - 1] + l;
            int l2 = suf[j];
            int r2 = suf[j] + l;

            if (c[l1] != c[l2] || c[r1] != c[r2]) c[suf[j]] = c[suf[j - 1]] + 1;
            else c[suf[j]] = c[suf[j - 1]];
        }
    }
}

void readString(string& str) {
    str = "";
    char c;

    scanf("%c",&c);
    while (c != '\n' && c != EOF) {
        str += c;
        scanf("%c",&c);
    }
}

int main() {
    string text;
    string findStr;
    vector<int> sufArray;

    cout<<"Input text:"<<endl;
    readString(text);

    getSufArray(sufArray, text);

    cout<<"Input substring to find:"<<endl;
    readString(findStr);

    cout<<"Substring indexes:"<<endl;
    binSearch(sufArray,text, findStr, 0, sufArray.size() - 1);

    system("pause");
    return 0;
}
